#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define LOG(...) fprintf(stderr,__VA_ARGS__)
using namespace std; using ll = long long;
constexpr int N=1.5e5+5;
#define k1 (k<<1)
#define k2 (k<<1|1)
int n,m,Q,a[N];
namespace Solve1{
	bool condition() { return n<=5000&&Q<=5000; }
	[[noreturn]] void Mian(){
		while(Q--){
			int l,r; cin>>l>>r;
			static ll p[N]; p[l]=0;
			For(i,l+1,r){
				p[i]=max(p[i-1],p[i-1]+a[i-1]-a[i]);
				if(i-m>=l) p[i]=max(p[i],p[i-m]+a[i-m]);
			}
			cout<<p[r]+a[r]<<'\n';
		}
		exit(0);
	}
}
namespace Solve2{
	bool condition() { return m<=100; }
	int L[N],R[N]; vector<int> qry[N<<2]; ll ans[N];
	void add(int k,int l,int r,int ql,int qr,int o){
		if(r-l+1<=m+5) return qry[k].push_back(o),void();
		int mid=(l+r)>>1;
		if(qr<=mid) add(k1,l,mid,ql,qr,o);
		else if(mid+1<=ql) add(k2,mid+1,r,ql,qr,o);
		else qry[k].push_back(o);
	}
	void solve(int k,int l,int r){
		if(r-l+1<=m+5){
			for(int o:qry[k]){
				static ll p[N]; p[L[o]]=0;
				For(i,L[o]+1,R[o]){
					p[i]=max(p[i-1],p[i-1]+a[i-1]-a[i]);
					if(i-m>=L[o]) p[i]=max(p[i],p[i-m]+a[i-m]);
				}
				ans[o]=p[R[o]];
			}
			return;
		}
		int mid=(l+r)>>1; solve(k1,l,mid); solve(k2,mid+1,r);
		For(t,mid-m/2-1,mid+m/2+1) if(l<=t&&t<=r) {
			static ll dis[N]; dis[t]=0;
			Rev(i,t-1,l){
				dis[i]=max(dis[i+1],dis[i+1]+a[i]-a[i+1]);
				if(i+m<=t) dis[i]=max(dis[i],dis[i+m]+a[i]);
			}
			For(i,t+1,r){
				dis[i]=max(dis[i-1],dis[i-1]+a[i-1]-a[i]);
				if(i-m>=t) dis[i]=max(dis[i],dis[i-m]+a[i-m]);
			}
			for(int o:qry[k]){
				if(L[o]<=t&&t<=R[o]) ans[o]=max(ans[o],dis[L[o]]+dis[R[o]]);
			}
		}
	}
	[[noreturn]] void Mian(){
		For(i,1,Q) cin>>L[i]>>R[i],add(1,1,n,L[i],R[i],i);
		solve(1,1,n); For(i,1,Q) cout<<ans[i]+a[R[i]]<<'\n';; exit(0);
	}
}
namespace Solve3{
	bool condition() { For(i,1,n-1) if(a[i]>a[i+1]) return false;; return true; }
	[[noreturn]] void Mian(){
		static ll sum[N]; For(i,1,n) sum[i]=(i>=m+1?sum[i-m]:0)+a[i];
		while(Q--){
			int l,r; cin>>l>>r;
			int k=r-l+1; k=(k+m-1)/m*m;
			cout<<sum[r]-(k<=r?sum[r-k]:0)<<'\n';
		}
		exit(0);
	}
}
namespace Solve4{
	bool condition() { return m>=n/2; }
	[[noreturn]] void Mian(){
		static ll sum[N]; For(i,1,n-1) sum[i]=sum[i-1]+max(0,a[i]-a[i+1]);
		static ll mx[19][N]; For(i,m+1,n) mx[0][i]=a[i-m]+sum[i-m-1]-sum[i-1];
		For(k,1,18) For(i,1,n-(1<<k)+1) mx[k][i]=max(mx[k-1][i],mx[k-1][i+(1<<(k-1))]);
		auto get=[&](int l,int r){
			int k=__lg(r-l+1); return max(mx[k][l],mx[k][r-(1<<k)+1]);
		};
		while(Q--){
			int l,r; cin>>l>>r;
			ll ans=sum[r-1]-sum[l-1];
			if(l+m<=r) ans=max(ans,get(l+m,r)-sum[l-1]+sum[r-1]);
			cout<<ans+a[r]<<'\n';
		}
		exit(0);
	}
}
int main(){
	Fin("clear.in"); Fout("clear.out");
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>Q; For(i,1,n) cin>>a[i];
	if(Solve1::condition()) Solve1::Mian();
	if(Solve2::condition()) Solve2::Mian();
	if(Solve3::condition()) Solve3::Mian();
	if(Solve4::condition()) Solve4::Mian();
	cerr<<"yiw\n";
	Solve1::Mian();
	return 0;
}